package com.lims.algorithm.algset.graph.basic;

import java.text.MessageFormat;
import java.util.Arrays;

/**
 * <功能简述>有向图 邻接矩阵
 *
 * @author lims
 * @date 2020-08-19 10:45
 */
public class MatrixDG extends GraphMatrixAbs<Character> {
    /**
     * 手动输入构造图
     */
    public MatrixDG() {
        // 输入"顶点数"和"边数"
        System.out.printf("input vertex number: ");
        int vlen = readInt();
        System.out.printf("input edge number: ");
        int elen = readInt();
        // 一堆点集中两两组合有多少种组合方式就有多少边（组合问题）
        if (vlen < 1 || elen < 1 || (elen > (vlen * (vlen - 1)))) {
            System.out.printf("input error: invalid parameters!\n");
            return;
        }

        // 初始化顶点
        vertes = new Character[vlen];
        for (int i = 0; i < vlen; i++) {
            System.out.printf("vertex(%d): ", i);
            vertes[i] = readChar();
        }

        // 初始化边
        edges = new int[vlen][vlen];
        for (int i = 0; i < elen; i++) {
            System.out.println(MessageFormat.format("输入第{0}条边的第{1}个顶点:", i + 1, 1));
            char c1 = readChar();
            System.out.println(MessageFormat.format("输入第{0}条边的第{1}个顶点:", i + 1, 2));
            char c2 = readChar();

            int p1 = getPosition(c1);
            int p2 = getPosition(c2);

            if (p1 == -1 || p2 == -1) {
                System.out.printf("input error: invalid edge!\n");
                return;
            }

            // 无向图对称
            edges[p1][p2] = 1;
        }
    }

    /**
     * 已知点集和边集构造图
     *
     * @param vexs  顶点集
     * @param edges 边集
     */
    public MatrixDG(Character[] vexs, Character[][] edges) {
        // 顶点数
        int vlen = vexs.length;
        // 边数
        int elen = edges.length;

        //vertes = new char[vlen];
        // 顶点集
        vertes = Arrays.copyOfRange(vexs, 0, vexs.length);

        //初始化边
        this.edges = new int[vlen][vlen];
        for (int i = 0; i < elen; i++) {
            // 两个顶点一条边
            int p1 = getPosition(edges[i][0]);
            int p2 = getPosition(edges[i][1]);

            // 无向图对称
            this.edges[p1][p2] = 1;
        }
    }

    /***********************************************************/
    public static void main(String[] args) {
        Character[] vexs = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
        Character[][] edges = new Character[][]{
                {'A', 'B'},
                {'B', 'C'},
                {'B', 'E'},
                {'B', 'F'},
                {'C', 'E'},
                {'D', 'C'},
                {'E', 'B'},
                {'E', 'D'},
                {'F', 'G'}};
        MatrixDG pG;

        // 自定义"图"(输入矩阵队列)
        //pG = new MatrixDG();
        // 采用已有的"图"
        pG = new MatrixDG(vexs, edges);

        pG.print();   // 打印图
    }
}
